package leetcode.editor.cn;

import java.util.Arrays;

/**
 * 完全平方数
 * @author qulq
 * @date 2024-07-25 21:39:59
 */
public class T279_PerfectSquares{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T279_PerfectSquares().new Solution();
	 }

	/**
	 * 完全背包：完全平方数是物品、n是背包
	 * f[i] = min(f[i], f[i-j*j]+1 | 0<= j <= i)
	 *
	 * f[1] = min(f[1], f[1-1] + 1) = 1，所以f[0] = 0
	 *
	 */

// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numSquares(int n) {
		int[] dp = new int[n + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		for (int i = 1; i * i <= n; i++) {
			for (int j = i * i; j <= n; j++) {
				dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
			}
		}
		return dp[n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}